package leecode

func permute(nums []int) (result [][]int) {
	path := make([]int, 0, len(nums))
	var backtracking func(used []bool)
	backtracking = func(used []bool) {
		if len(path) == len(nums) {
			temp := make([]int, len(path))
			copy(temp, path)
			result = append(result, temp)
			return
		}
		for i := 0; i < len(nums); i++ {
			//如果该元素被使用过了, 跳过
			if used[i] == true {
				continue
			}
			used[i] = true
			path = append(path, nums[i])
			backtracking(used)
			path = path[:len(path)-1]
			used[i] = false
		}
	}
	used := make([]bool, len(nums))
	used = append(used, false)
	backtracking(used)
	return
}
